package automaton;

import java.util.ArrayList;
import java.util.HashMap;

import dk.brics.automaton.*;

/**
 * @author UserXP
 * this class gets "#" separated labels route and create the query automaton
 * which accepts all xpath queries (\,\\,*) which starts with the path root and
 * ends at the final label 
 */
public class QueryAutomaton {
	
	//will hold the label's route
	ArrayList<String> _labels = new ArrayList<String>();
	
	
	/**
	 * @author UserXP
	 * an helper class which represents a detailed version of the automaton's states
	 * its a state, data about from where and how we got to this state
	 */
	private class MyState
	{
		//the query that progress us from the state's father to this state
		public String query;
		
		//all nodes that can be reached from the state's father with the query
		public ArrayList<Integer> nodesId;
		
		//state's father
		public MyState father;
		
		//default ctor
		public MyState()
		{
			nodesId = new ArrayList<Integer>();
			father = null;
		}
		
		public String toString()
		{
			String ans = "";
			for(int i = 0 ; i < nodesId.size() - 1 ; ++i)
			{
				ans+=(String.valueOf(nodesId.get(i)) + "#");
			}
			if (nodesId.size() > 0)
			{
				ans+=String.valueOf(nodesId.get(nodesId.size()-1));
			}
			
			return ans;
		}
		
		public int hashCode()
		{
//			System.out.println("NodesIds = " + nodesId.toString() + " Hash: " + toString().hashCode());
			return toString().hashCode();
		}
		
		public boolean equals(Object other)
		{
//			System.out.println("Equals: Cur = " + hashCode() + " Other = " + other.hashCode());
			return hashCode() == other.hashCode();
		}
		
		/*public void printQuery()
		{
			System.out.println(query);
		}*/
	}
	
	
	/**
	 * this method gets nodeIndex and it's father and generates 2 children states
	 * one can be reached via \* and one via \label when label is the next node's label
	 * 
	 * for example: the next path r-a-b-c, 'a' children is \* and \b both will progress
	 * the state from 'a' to 'b'
	 * 
	 * @param father
	 * @param nodeIndex
	 * @return
	 */
	private ArrayList<MyState> GetChildrens(MyState father,int nodeIndex)
	{
		ArrayList<MyState> childrens = new ArrayList<MyState>();
		
		if (nodeIndex < _labels.size() - 1)
		{
			MyState n0 = new MyState(),n1 = new MyState();
			n0.query = "\\" + _labels.get(nodeIndex+1);
			n0.nodesId.add(nodeIndex+1);
			n0.father = father;
			childrens.add(n0);
			
			n1.query = "\\*";
			n1.nodesId.add(nodeIndex+1);
			childrens.add(n1);
			n1.father = father;
		}
		
		return childrens;
	}
/*	
	private ArrayList<String> GetUniqueLabels()
	{
		HashMap<String, String> helper = new HashMap<String, String>();
		ArrayList<String> uniqueLabels = new ArrayList<String>();
		for(String label:_labels)
		{
			if (!helper.containsKey(label))
			{
				helper.put(label, "");
				uniqueLabels.add(label);
			}
		}
*/	
	
	/**
	 * this helper function will add some node as a descendant of a given father
	 * @param father
	 * @param descendants
	 * @param queryToStateMap will store queries that we used before
	 * @param nodeIndex
	 */
	private void AddDescendant(MyState father,ArrayList<MyState> descendants,HashMap<String, MyState> queryToStateMap,int nodeIndex)
	{
		//since every node can be reached through \\*, check if we have this query,
		//if not, create it and add the node's id to it's list.
		if (!queryToStateMap.containsKey("\\\\*"))
		{
			MyState star = new MyState();
			star.query = "\\\\*";
			star.father = father;
			queryToStateMap.put(star.query, star);
			descendants.add(star);
		}
		queryToStateMap.get("\\\\*").nodesId.add(nodeIndex);
		
		String descendantLabel = _labels.get(nodeIndex);
		
		//check if the query \\descendantLabel exists, if so, just add the node's id to
		//the query's list, if not, create new one.
		if (!queryToStateMap.containsKey("\\\\" + descendantLabel))
		{
			MyState s = new MyState();
			s.query = "\\\\" + descendantLabel;
			s.father = father;
			queryToStateMap.put(s.query, s);
			descendants.add(s);
		}
		
		queryToStateMap.get("\\\\"+descendantLabel).nodesId.add(nodeIndex);
		
	}
	
	/**
	 * this method gets node index and node's father and generates all states that can be
	 * reached via \\ operator.
	 * 
	 * for example: the next path: r-a-b-c, all queries that will return nodes below 'a' are:
	 * 				\\b,\\c,\\*
 
	 * @param father
	 * @param nodeIndex
	 * @return
	 */
	private ArrayList<MyState> GetDescendants(MyState father,int nodeIndex)
	{
		ArrayList<MyState> descendants = new ArrayList<MyState>();
		
		HashMap<String, MyState> queryToStateMap = new HashMap<String, MyState>();
		
		//go over node's descendants and generate all states that can be reached from the
		//given node (state)
		for(int i = nodeIndex + 1 ; i < _labels.size() ; ++i)
		{
			AddDescendant(father,descendants, queryToStateMap, i);
		}
				
		return descendants;
	}
	
	
	/**
	 * this helper function gets state and returns all states that can be reached from
	 * this sate via \ or via \\ operators
	 * @param s
	 * @return
	 */
	private ArrayList<MyState> GetNextStates(MyState s)
	{
		
		ArrayList<MyState> nextStates = new ArrayList<QueryAutomaton.MyState>();
		
		for(int index:s.nodesId)
		{
			ArrayList<MyState> childrens = GetChildrens(s,index);
			ArrayList<MyState> descendants = GetDescendants(s,index);
		
			nextStates.addAll(childrens);
			nextStates.addAll(descendants);
		}
		
		return nextStates;
		
		
		
	}
	
	/**
	 * this helper function gets an automaton's state and concatenate set of states 
	 * which represents pass on a given word.
	 * 
	 *  for example, for state s and word "hello" we will get the next settings:
	 *  s -> s0 -> s1 -> s2 -> s3 -> s4
	 *     h     e    l     l      o
	 *  
	 *  s4 will be returned
	 *  
	 * @param s
	 * @param word
	 * @return
	 */
	private State AddWord(State s,String word)
	{
		//System.out.println("adding new word " + word);
		for(char ch:word.toCharArray())
		{
			State nextState = new State();
			s.addTransition(new Transition(ch, nextState));
			s = nextState;
		}
		
		return s;
	}
	
	/**
	 * just like the other AddWord method, just here the last state will be "end" and not
	 * new state
	 * @param start
	 * @param end
	 * @param word
	 */
	private void AddWord(State start,State end,String word)
	{
		//System.out.println("connect states with word: " + word);
		if (word.length() > 0)
		{
			//add the word without the last char, and concatenate the last state with "end"
			//state using the word's last char
			AddWord(start,word.substring(0, word.length()-1)).addTransition(new Transition(word.charAt(word.length()-1), end));
		}
		
	}
	
	/**
	 * this method gets '#' separated route and generate the automaton which accepts all
	 * queries that start at the route's beginning and ends at the route last's label. 
	 * @param route
	 * @return
	 */
	public Automaton CreateQueriesAutomaton(ArrayList<String> labelRoute)
	{
		Automaton A = new Automaton();
		State s = new State();
		A.setInitialState(s);
		MyState root = new MyState();
		root.nodesId.add(0);
		
		HashMap<MyState, State> duplicaionHelper = new HashMap<MyState, State>();
		duplicaionHelper.put(root, s);
		
		_labels = labelRoute;
		
		ArrayList<MyState> statesQueue = GetNextStates(root);
		
		//while we have states to handle
		while(!statesQueue.isEmpty())
		{
			//remove last unhandle state
			MyState curState = statesQueue.remove(statesQueue.size() - 1);
			
			//if this state can be reached through another query already, just link
			//the state's father to this state with the curState query
			if (duplicaionHelper.containsKey(curState))
			{
				//get the state that can we already have
				State sameState = duplicaionHelper.get(curState);
				//get curState father
				State father = duplicaionHelper.get(curState.father);
				
				//link the father with sameState with the curState's query
				AddWord(father, sameState,curState.query);
				
			}
			else
			{
				//create automaton state and update duplication helper
				State newState = AddWord(duplicaionHelper.get(curState.father),curState.query);
				
				//this state will accept only if one of the states that can be reached from it
				//is the last label
				newState.setAccept(curState.nodesId.contains(_labels.size() -  1));
				
				duplicaionHelper.put(curState, newState);
				
				
				//add children and descendants to queue
				statesQueue.addAll(GetNextStates(curState));
				
			}
		}
		A = AutomatonUtils.StableAutomaton(A);
		//minimize the new automaton for better performance
		A.minimize();
		return A;
	}
	
	public void test()
	{
		
		ArrayList<Integer> tt = new ArrayList<Integer>();
		
		tt.add(1);
		
		System.out.println(new Integer(1).equals(new Integer(1)));
		System.out.println(new Integer(1) == new Integer(1));
		System.exit(0);
		
		HashMap<MyState, State> b = new HashMap<MyState, State>();
		
		MyState s = new MyState();
		s.query = "ABC";
		s.nodesId.add(1);
		//System.out.println(s.hashCode());
		b.put(s, null);
		
		MyState r = new MyState();
		r.query = "DEF";
		r.nodesId.add(1);
		//System.out.println(r.hashCode());
		System.out.println(b.containsKey(r));
	}
	
	public static void main(String[] args)
	{
		System.out.println(new Automaton().getInitialState());
		ArrayList<String> labels = new ArrayList<String>();
		labels.add("r");
		labels.add("a");
		labels.add("a");
		
		Automaton A = new QueryAutomaton().CreateQueriesAutomaton(labels);
		System.out.println(new QueryAutomaton().CreateQueriesAutomaton(labels).getFiniteStrings());
		System.out.println(A.run("\\\\*"));
		//System.out.println(A.getInitialState().step('t').step('a').isAccept());
	}
}
